package rickyGame.game.scene
{
	import flash.display.DisplayObject;
	import flash.display.DisplayObjectContainer;
	import flash.display.Sprite;
	import flash.utils.Dictionary;
	
	import ricky.quadtree.Leaf;
	import ricky.quadtree.Quadtree;

	/**
	 * 修改了 paillip
	 * ...
	 * @author Phillip Chertok
	 */
	public class Pathfinder
	{
		public static var heuristic:Function = Pathfinder.euclidianHeuristic;	
		public static var MAX_SEARSH_STEP:uint=500;
		public static var stage:Sprite;
		/**
		 * 简单寻路目标可以是阻挡 无法找到最佳路径 寻路速度快</br>
		 * 参数：</br>
		 * firstNode:Leaf 第一个节点	</br>
		 * destinationNode:Leaf		目标节点</br>
		 * tree:Quadtree 搜索的树</br>
		 * traversableFunction:Function(arr:int):Boolean 检查是否可以行走
		 */
		public static function findPath1( firstNode:Leaf, destinationNode:Leaf, tree:Quadtree,traversableFunction:Function,asType:String):Array 
		{
			var maxStep:int=0;
			
			var openNodes:Array = [];
			var closedNodes:Array = [];			
			
			var currentNode:Leaf = firstNode;
			var testNode:Leaf;
			
			var l:int;
			var i:int;
			
			var connectedNodes:Array;
			var travelCost:Number = 1.0;//花费
			var path:Array=new Array();
			var children:Array=new Array();
			
			var g:Number;
			var h:Number;//估值函数
			var f:Number;
			
			var currF:Number;
			var currG:Number;
			var currH:Number;
			
			currG = 0;
			currH = Pathfinder.heuristic(currentNode, destinationNode, travelCost);
			currF = currG + currH;//当前代价
			
//			JDebug.trace("开始搜索："+currentNode+"目标节点："+destinationNode);
			
			while (currentNode != destinationNode) {
				
				maxStep++;
				if(maxStep>MAX_SEARSH_STEP)
					return path;
				
				connectedNodes = connectedNodeFunction( currentNode,tree );//收集周围的8个节点			
				children.length=0;
				l = connectedNodes.length;
//				drawNode(currentNode,0xff0000);
				
				for (i = 0; i < l; ++i) {
					
					testNode = connectedNodes[i];
					
					if (testNode == currentNode || !traversableFunction(asType,testNode)) continue;//如果是当前节点跳出	 testNode.traversable==false			
					
					g = currentNode.attr + travelCost;
					
//					drawNode(testNode);

					//判断是否已经进算过
					if ( Pathfinder.isOpen(testNode, openNodes))
					{
						if(testNode.f<currentNode.f)
							return path;
					}
					else if(Pathfinder.isClosed( testNode, closedNodes) )
					{

					}
					else {
						h = Pathfinder.heuristic( testNode, destinationNode, travelCost);//计算估值
						f = g + h;
						testNode.f = f;//计算f值
						openNodes.push(testNode);//放入开放节点中
						children.push(testNode);
					}

				}
				closedNodes.push( currentNode );//已经搜索完周围坐标放入关闭节点
				
				if (openNodes.length == 0) {
					return null;
				}
				
				if(children.length==0)
					return path;
				
				children.sortOn('f', Array.NUMERIC);
				currentNode = children.shift() as Leaf;//找到f值最小的的节点
				
				path.push(currentNode);
			}
			
			return path;
		}
		
		/**
		 * 最佳路径寻路</br>
		 * 参数：</br>
		 * firstNode:Leaf 第一个节点	</br>
		 * destinationNode:Leaf		目标节点(必须可走哦)</br>
		 * tree:Quadtree 搜索的树</br>
		 * traversableFunction:Function(arr:int):Boolean 检查是否可以行走
		 */
		public static function findPath( firstNode:Leaf, destinationNode:Leaf, tree:Quadtree,traversableFunction:Function,asType:String):Array 
		{
			var maxStep:int=0;
			
			var openNodes:Array = [];
			var closedNodes:Array = [];			
			
			var currentNode:Leaf = firstNode;
			var testNode:Leaf;
			
			var l:int;
			var i:int;
			
			var connectedNodes:Array;
			var travelCost:Number = 1.0;//花费
			var path:Array=new Array();
			var parent:Dictionary=new Dictionary();
			
			var g:Number;
			var h:Number;//估值函数
			var f:Number;
			
			var currF:Number;
			var currG:Number;
			var currH:Number;
			
			currG = 0;
			currH = Pathfinder.heuristic(currentNode, destinationNode, travelCost);
			currF = currG + currH;//当前代价
			
//			JDebug.trace("开始搜索："+currentNode+"目标节点："+destinationNode);
			
			while (currentNode != destinationNode) {
				
				maxStep++;
				if(maxStep>MAX_SEARSH_STEP)
					return path;
				
				connectedNodes = connectedNodeFunction( currentNode,tree );//收集周围的8个节点			

				l = connectedNodes.length;
//				drawNode(currentNode,0xff0000);
				
				for (i = 0; i < l; ++i) {
					
					testNode = connectedNodes[i];
					
					if (testNode == currentNode || !traversableFunction(asType,testNode)) continue;//如果是当前节点跳出	 testNode.traversable==false			
					
					g = 0 + travelCost;
					h = Pathfinder.heuristic( testNode, destinationNode, travelCost);
					f = g + h;
					
//					drawNode(testNode);
					
					//判断是否已经进算过
					if ( Pathfinder.isOpen(testNode, openNodes) || Pathfinder.isClosed( testNode, closedNodes) )//如果没搜索过
					{
						if(testNode.f > f)
						{
							testNode.f = f;
							parent[testNode.toString()]=currentNode;
						}
					}
					else {
						testNode.f = f;//计算f值
						parent[testNode.toString()]=currentNode;
						openNodes.push(testNode);//放入开放节点中
					}
					
				}
				closedNodes.push( currentNode );//已经搜索完周围坐标放入关闭节点
				
				if (openNodes.length == 0) {
					return null;
				}
				
				openNodes.sortOn('f', Array.NUMERIC);
				currentNode = openNodes.shift() as Leaf;//找到f值最小的的节点
				
				if(path.indexOf(currentNode)==-1)
					path.push(currentNode);
			}
			
			path.length=0;
			//生成最佳路径
			var node:Leaf = destinationNode;//目标路径
			path.push(node);
			while (node != firstNode) {
				node = parent[node.toString()];
				if(!node)
					break;
				if(path.indexOf(node)==-1)
					path.unshift( node );
//				break;
			}
			
			return path;
		}
		/**
		 * 创建返回路径</br>
		 * 参数</br>
		 * destinationNode:Leaf 目标节点 </br>
		 * startNode:Leaf 开始节点 </br>
		 */
		public static function buildPath(destinationNode:Leaf, startNode:Leaf,parent:Dictionary):Array {			
			var path:Array = [];
			var node:Leaf = destinationNode;
			path.push(node);
			while (node != startNode) {
				node = parent[node.toString()];
				if(!node)
					break;
				path.unshift( node );
			}
			
			return path;			
		}
		
		/**
		 * 阻挡判断函数</br>
		 * 参数:</br>
		 * obj:Pu 玩家对象</br>
		 * leaf:Leaf 格子属性</br>
		 */
		public static function traversableFunction(asType:String,leaf:Leaf):Boolean
		{
			switch(asType)
			{
				case "fly":
					return true;
				case "ground":
					if(leaf.attr<=2 )
						return true;
					return false;
				case "river":
					if(leaf.attr==3 )
						return true;
					return false;
					
			}
			
			return true;
		}
		
		/**
		 * 阻挡判断函数 包括周围玩家</br>
		 * 参数:</br>
		 * obj:Pu 玩家对象</br>
		 * leaf:Leaf 叶子属性</br>
		 */
		public static function traversableAroundFunction(asType:String,leaf:Leaf):Boolean
		{
			if(leaf.objects && leaf.objects.length)
			{
				return false;
			}
			
			switch(asType)
			{
				case "fly":
					return true;
				case "ground":
					if(leaf.attr<=2 )
						return true;
					return false;
				case "river":
					if(leaf.attr<=3 )
						return true;
					return false;
			}
			
			return false;
		}
		
		private static function drawNode(leaf:Leaf,color:uint=0x0fff00):void
		{
			if(stage)
			{
				stage.graphics.beginFill(color,0.7);
				var vx:Number=leaf.x*Common.tileWidth+20;
				var vy:Number=leaf.y*Common.tileHeight+15;
				stage.graphics.drawRect(vx,vy,4,3);
				stage.graphics.endFill();
			}
		}
		
		public static function drawPath(arr:Array,sprit:Sprite):void
		{
			var l:int=arr.length;
			var g:Leaf,vx:Number,vy:Number;
//			sprit.graphics.clear();
			sprit.graphics.beginFill(0xffff00,0.7);
			for(var i:int=0;i<l;i++)
			{
				g=arr[i];
				vx=g.x*Common.tileWidth;
				vy=g.y*Common.tileHeight;
				sprit.graphics.drawRect(vx,vy,4,3);
			}
			sprit.graphics.endFill();
		}
		
		public static function clearPath(leaf:Leaf,sprit:Sprite):void
		{
			var g:Leaf,vx:Number,vy:Number;
//			sprit.graphics.clear();
			sprit.graphics.beginFill(0x000000,1);
		    vx=leaf.x*Common.tileWidth;
			vy=leaf.y*Common.tileHeight;
			sprit.graphics.drawRect(vx,vy,8,6);
			sprit.graphics.endFill();
		}
		
		/**
		* 寻找周围8个节点
		*/
		public static function connectedNodeFunction(node:Leaf,tree:Quadtree):Array
		{
			var array:Array=tree.getAroundLeaf(node.x,node.y,1);
			return array;
		}
		
		/**
		 * 是否开发节点
		 */
		public static function isOpen(node:*, openNodes:Array):Boolean {
			
			var l:int = openNodes.length;
			for (var i:int = 0; i < l; ++i) {
				if ( openNodes[i] == node ) return true;
			}
			
			return false;			
		}
		
		/**
		 * 是否关闭节点
		 */
		public static function isClosed(node:*, closedNodes:Array):Boolean {
			
			var l:int = closedNodes.length;
			for (var i:int = 0; i < l; ++i) {
				if (closedNodes[i] == node ) return true;
			}
			
			return false;
		}
		
		/****************************************************************************** 
		*
		*	These are our avaailable heuristics 
		*
		******************************************************************************/		
		/**
		 * 欧几里德 估值函数
		 */
		public static function euclidianHeuristic(node:Leaf, destinationNode:Leaf, cost:Number = 1.0):Number
		{
			var dx:Number = (node.x - destinationNode.x)*Common.tileWidth;
			var dy:Number = (node.y - destinationNode.y)*Common.tileHeight;
			
			return Math.sqrt( dx * dx + dy * dy ) * cost;
		}
		
		/**
		 * 曼哈顿 估值函数
		 */
		public static function manhattanHeuristic(node:Leaf, destinationNode:Leaf, cost:Number = 1.0):Number
		{
			return Math.abs(node.x - destinationNode.x)*Common.tileWidth * cost + 
				   Math.abs(node.y + destinationNode.y)*Common.tileHeight * cost;
		}
		
		/**
		 * 对角线 估值函数
		 */
		public static function diagonalHeuristic(node:Leaf, destinationNode:Leaf, cost:Number = 1.0, diagonalCost:Number = 1.0):Number
		{
			var dx:Number = Math.abs(node.x - destinationNode.x)*Common.tileWidth;
			var dy:Number = Math.abs(node.y - destinationNode.y)*Common.tileHeight;
			
			var diag:Number = Math.min( dx, dy );
			var straight:Number = dx + dy;
			
			return diagonalCost * diag + cost * (straight - 2 * diag);
		}
		
	}
}